//有重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合。
//
// 示例1:
//
//  输入：S = "qqe"
// 输出：["eqq","qeq","qqe"]
//
//
// 示例2:
//
//  输入：S = "ab"
// 输出：["ab", "ba"]
//
//
// 提示:
//
//
// 字符都是英文字母。
// 字符串长度在[1, 9]之间。
//
//
// Related Topics 字符串 回溯与递归 👍 88 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
// 这就相当于全排列II的解法
function permutation(S: string): string[] {

    function backtracking(S,temp) {
        if (temp.length === S.length) {
            res.push(temp.join(''))
            return
        }
        for (let i = 0; i < S.length; i ++) {
            if (i > 0 && S[i] === S[i - 1] && usedArr[i - 1] === false) continue;
            if (usedArr[i] === false) {
                temp.push(S[i])
                usedArr[i] = true
                backtracking(S,temp)
                usedArr[i] = false
                temp.pop()
            }
        }
    }
    let res : string[] = []
    // 对于排列问题，树层上去重和树枝上去重，都是可以的，但是树层上去重效率更高！
    const usedArr: boolean[] = new Array(S.length).fill(false);
    S = Array.from(S).sort((a, b) => a.charCodeAt(0) - b.charCodeAt(0)).join('')
    backtracking(S,[])
    return res

};
//leetcode submit region end(Prohibit modification and deletion)
//有重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合。
//
// 示例1:
//
//  输入：S = "qqe"
// 输出：["eqq","qeq","qqe"]
//
//
// 示例2:
//
//  输入：S = "ab"
// 输出：["ab", "ba"]
//
//
// 提示:
//
//
// 字符都是英文字母。
// 字符串长度在[1, 9]之间。
//
//
// Related Topics 字符串 回溯与递归 👍 88 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
// 这种方法 用Set存放可以直接去重了  用vis数组来节约时间 这个vis数组相当于树枝去重了 在树层上的重复由Set来管
function permutation2(S: string): string[] {

    function backtracking(S,temp) {
        if (temp.length === S.length) {
            res.add(temp.join(''))
            return
        }
        for (let i = 0; i < S.length; i ++) {
            if (vis[i]) continue
            vis[i] = true
            temp.push(S[i])
            backtracking(S,temp)
            vis[i] = false
            temp.pop()
        }
    }
    let res : Set<string> = new Set<string>()
    let vis : boolean[] = []
    backtracking(S,[])
    return Array.from(res)

};
//leetcode submit region end(Prohibit modification and deletion)
